package 简单.前缀和与差分;

/**
 * 给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个
 * 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
 * 「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-score-after-splitting-a-string
 */
public class 分割字符串的最大得分_1422 {

    public static void main(String[] args) {

        System.out.println(maxScore("011101"));

    }

    /**
     * 前缀和
     *
     * @param s
     * @return
     */
    public static int maxScore(String s) {
        int maxCount = 0;
        int[] countZero = new int[s.length()];
        int[] countOne = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            int oneIdx = s.length() - 1 - i;
            if (i != 0) {
                countZero[i] = countZero[i - 1];
                countOne[oneIdx] = countOne[oneIdx + 1];
            }
            if ('0' == s.charAt(i)) {
                countZero[i]++;
            }
            if ('1' == s.charAt(oneIdx)) {
                countOne[oneIdx]++;
            }
        }

        for (int i = 0; i < s.length() - 1; i++) {
            maxCount = Math.max(maxCount, countZero[i] + countOne[i + 1]);
        }
        return maxCount;
    }

}
